#
# @lc app=leetcode.cn id=33 lang=python3
#
# [33] 搜索旋转排序数组
#

# @lc code=start
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        if n == 0:
            return -1
        left, right = 0, n - 1
        
        while left < right:
            # 使用上取整的中间数, 括号里 + 1
            mid = (left + right + 1) >> 1
            
            # 右边一定有序
            if nums[mid] < nums[right]:
                # 在有序区间
                if nums[mid] <= target and target <= nums[right]:
                    # 下一轮搜索区间 [mid, right]
                    left = mid
                # 非有序区间
                else:
                    # 下一轮搜索区间 [left, mid-1]
                    right = mid - 1
            # 左边一定有序
            else:
                # [left, mid]有序，当区间只有两个元素
                # mid = (left + right + 1) >> 1 一定取右边，mid-1不会越界
                if nums[left] <= target and target <= nums[mid-1]:
                    # 下一轮搜索区间
                    right = mid - 1
                else:
                    left = mid
        
        return left if nums[left] == target else -1
# @lc code=end

